package com.jiang.daily.Q1278;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/03/03 13:12
 */
class Solution {
    // public int palindromePartition(String s, int k) {
    //     int n = s.length();
    //     int[][] dp = new int[n + 1][k + 1]; // 对于字符串 S 的前 i 个字符，将它分割成 j 个非空且不相交的回文串，最少需要修改的字符数
    //     for (int i = 1; i <= n; i++) {
    //         Arrays.fill(dp[i], Integer.MAX_VALUE);
    //     }

    //     char[] arr = s.toCharArray();

    //     for (int i = 1; i <= n; i++) {
    //         int cnt = Math.min(i, k); // 回文串最多个数
    //         for (int j = 1; j <= cnt; j++) {
    //             if (j == 1) {
    //                 dp[i][j] = cost(0, i - 1, arr);
    //             } else {
    //                 for (int i0 = j - 1; i0 < i; i0++) {
    //                     dp[i][j] = Math.min(dp[i][j], dp[i0][j - 1] + cost(i0, i - 1, arr));
    //                 }
    //             }
    //         }
    //     }

    //     return dp[n][k];
    // }

    // 优化
    public int palindromePartition(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();

        int[][] cost = new int[n][n]; // 索引为 i ~ j 子字符串构成回文子串需要修改的字符数
        for (int span = 1; span < n; span++) {
            for (int i = 0; i < n - span; i++) {
                int j = i + span;
                cost[i][j] = cost[i + 1][j - 1] + (arr[i] == arr[j] ? 0 : 1);
            }
        }


        int[][] dp = new int[n + 1][k + 1]; // 对于字符串 S 的前 i 个字符，将它分割成 j 个非空且不相交的回文串，最少需要修改的字符数
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }

        for (int i = 1; i <= n; i++) {
            int cnt = Math.min(i, k); // 回文串最多个数
            for (int j = 1; j <= cnt; j++) {
                if (j == 1) {
                    dp[i][j] = cost[0][i - 1];
                } else {
                    for (int i0 = j - 1; i0 < i; i0++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i0][j - 1] + cost[i0][i - 1]);
                    }
                }
            }
        }

        return dp[n][k];
    }

    private int cost(int l, int r, char[] arr) {
        int res = 0;
        while (l < r) {
            if (arr[l] != arr[r]) res++;
            l++;
            r--;
        }
        return res;
    }
}
